package 简单.动态规划.子序列;

/**
 * 给定一个整数数组 nums ，找到一个
 * 具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * <p>
 * 来源：https://leetcode-cn.com/problems/maximum-subarray/
 */
public class 最大子序和_53 {

    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(efficientMaxSubArray(nums));
    }

    //最大子数组可以是nums任何一个元素开头
    public static int maxSubArray(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        //表示最大和
        int maxProfit = nums[0];
        for (int i = 0; i < nums.length - 1; i++) {
            int j = i;
            //表示从i的位置到最后一个元素相加的和
            int curProfit = nums[i];
            while (j < nums.length - 1) {
                j++;
                maxProfit = curProfit > maxProfit ? curProfit : maxProfit;
                curProfit = curProfit + nums[j];
                maxProfit = curProfit > maxProfit ? curProfit : maxProfit;
            }
        }
        //最大子数组是最后一个元素时的情况
        return maxProfit > nums[nums.length - 1] ? maxProfit : nums[nums.length - 1];
    }

    /**
     * 动态规划，为了更好的理解，将子问题定义为由某一个元素结尾的最大和的连续子数组，让计算顺序为从首到尾
     * a. 定义子问题(分析开头特殊情况的值)
     * 由第1个元素结尾的最大和的连续子数组是多少
     * 由第2个元素结尾的最大和的连续子数组是多少
     * ...
     * b. 写出子问题的递推关系
     * 因为是连续的，第2个元素结尾的最大和的连续子数组=第1个元素结尾的最大和+nums[1]
     * 但是，当dp[i-1]<=0时，dp[i]的最大和，就是nums[i]
     * <p>
     * c. 确定DP数组的计算顺序
     * 从首到尾
     * d. 空间优化
     */
    public static int maxSubArray1(int[] nums) {
        int maxProfit = nums[0];
        //预留一位，dp[i]表示nums数组的第i位元素
        int[] dp = new int[nums.length + 1];
        for (int i = 2; i < dp.length; i++) {
            dp[0] = 0;
            dp[1] = nums[0];
            if (dp[i - 1] >= 0) {
                dp[i] = dp[i - 1] + nums[i - 1];
            } else {
                dp[i] = nums[i - 1];
            }
            maxProfit = maxProfit > dp[i] ? maxProfit : dp[i];
        }
        return maxProfit;
    }

    //空间优化，dp[i]只与dp[i-1]有关
    public static int efficientMaxSubArray(int[] nums) {
        int maxProfit = nums[0];
        int cur;
        int pre1 = 0;
        for (int i = 0; i < nums.length; i++) {
            //优化判断，如果pre1是负数，取num[i]
            cur = Math.max(pre1 + nums[i], nums[i]);
            maxProfit = Math.max(maxProfit, cur);
            pre1 = cur;
        }
        return maxProfit;
    }


}
